查看原文
其他

看雪.腾讯TSRC 2017 CTF 秋季赛 第五题点评及解析思路

2017-11-03 看雪CTF 看雪学院

看雪CTF快讯:

第五题已有13人破解!



导语

这道题的比赛过程可谓是精彩纷呈,十分有看点了。


群里的讨论十分火爆~大家都对这道题表达了自己的见解~


精彩的第五题结束,第五题出题者birchfire以13人的成绩,一举登上防守方第一位。


第五题过后,很多黑马让大家眼前一亮。

前十名的排名再次发生了较大的变动。poyoten升至第一名。

cqccqc冲进第四名,raycp、qwertyaa、acdxvfsvd,也是黑马,紧随其后,冲进了前十位。



第五题过去后,比赛的最终结果又开始变得扑朔迷离。

老将能否捍卫自己的宝座,而新将又是否能够一举夺魁,给我们带来新的惊喜呢?


接下来让我们一起来看看第五题的点评、出题思路和解析。



看雪评委netwind点评


本题构思精细、耐人寻味,是一道非常有趣的题目。首先作者通过int 2d 指令触发异常来进行反调试,然后采用魔方转动变换的方式对原始数据进行加密。而魔方旋转变换可以用矩阵乘法实现,通过乘以一个 48*48 的单位矩阵实现魔方的旋转变换,破解者需要分析加密过程,然后逆序操作进行解密。


第五题作者简介


brichfire,看雪论坛资深粉丝,喜欢程序逆向分析,长期从事基于污点传播方法的二进制代码分析和漏洞挖掘方法研究,特别感谢看雪论坛提供这么好的学习平台,喜欢的书有《0Day漏洞》、《Android软件安全与逆向分析》、《软件安全分析与应用》等。



第五题设计思路


算法思想


1、 本题采用魔方转动变换的方式对原始数据进行加密,破解者需要分析加密过程,然后逆序操作进行解密。


2、 魔方操作的数学建模
魔方初始状态图,中心 a,b,c,d,e,f 是 6 个面的中心,


10
11
12

17
b
13
16
15
14
40
41
42
0
1
2
20
21
22
47
e
43
7
a
3
27
c
23
46
45
44
6
5
4
26
25
24

30
31
32

37
d
33
36
35
34

50
51
52

57
f
53
56
55
54


顺时针旋转 a 面 90°得到如下图:红色的数字是发生了置换的位置。



10
11
12

17
b
13
44
43
42
40
41
30
6
7
0
16
21
22
47
e
31
5
a
1
15
c
23
46
45
32
4
3
2
14
25
24

30
31
32

37
d
33
36
35
34

50
51
52

57
f
53
56
55
54


顺时针旋转 b 面 90°得到如下图:



16
17
10

15
b
11
14
13
12
0
1
2
20
21
22
54
55
56
47
e
43
7
a
3
15
c
23
46
45
44
6
5
4
14
25
24

30
31
32

37
d
33
36
35
34

50
51
52

57
f
53
42
41
40


顺时针旋转 c 面 90°得到如下图:



10
11
2

17
b
3
16
15
4
40
41
42
0
1
32
26
27
20
47
e
43
7
a
33
25
c
21
46
45
44
6
5
34
24
23
22

30
31
52

37
d
53
36
35
54

50
51
12

57
f
13
56
55
14


顺时针旋转 d 面 90°得到如下图:



10
11
12

17
b
13
16
15
14
40
41
42
0
1
2
20
21
22
47
e
43
7
a
33
27
c
23
52
51
50
46
45
44
6
5
4

36
31
30

35
d
31
34
35
32

24
25
26

57
f
53
56
55
54


顺时针旋转 e 面 90°得到如下图:



50
11
12

57
b
13
56
15
14
46
47
40
10
1
2
20
21
22
45
e
41
17
a
3
27
c
23
44
43
42
16
5
4
26
25
24

0
31
32

7
d
33
6
35
34

30
51
52

37
f
53
36
55
54


顺时针旋转 f 面 90°得到如下图:



22
23
24

17
b
13
16
15
14
12
41
42
0
1
2
20
21
34
11
e
43
7
a
3
27
c
35
10
45
44
6
5
4
26
25
36

30
31
32

37
d
33
40
47
46

56
51
50

55
f
51
54
53
52


无论怎么旋转,魔方中心不会改变位置,每个面有 8 个值,上图中数为 8 进
制, 6 个面共 48 个数,可以构成一个 48*1 的矩阵。而魔方旋转变换可以用矩阵乘法实现,通过乘以一个 48*48 的单位矩阵实现魔方的旋转变换。 6 个面用 6 个矩阵分别表示:如果 a 面旋转 180°就乘以 2 次 MATRIX_a, 270°就乘以 3 次。 因此,每个面的操作有 3 种, 6 个面共计 18 种。为了将输入映射到操作,可以考虑 18 进制,而输入范围包括数字和大小写字母,可以考虑用 62 进制,两个结合到一块就是 62 进制到 18 进制的转换。

int MATRIX_a[48][48];
int MATRIX_b[48][48];
int MATRIX_c[48][48];
int MATRIX_d[48][48];
int MATRIX_e[48][48];
int MATRIX_f[48][48];


3、 加密密钥:KanXueCrackMe2017,题目将其视为 62 进制数(左边是低位,右边是高位),因为合法输入包含 26*2 个大小写字母和 10 个数字共计 62 个字符,加密前先转换成 18 进制数,EDAHE450C741GH441E11BH84(左边是低位,右边是高位), 每一位作为转动魔方的一个操作码 V,用 V/3 表示要操作的面(魔方 6 个面,编号 0~5),用 V%3 表示要转动的角度, 0, 1, 2 分别表 示 顺 时 针 转 动 90 ° , 180 ° , 270 ° , 初 始 化 时 依 次 按 照EDAHE450C741GH441E11BH84 对应的动作转动魔方,得到一个混乱状态的魔方。


4、 验证过程是用户输入验证码,数字和大小写字母组合成一个 62 进制的数,
然后转换成 18 进制的数据,从低位到高位作为魔方转动的操作对魔方进行
变换,结束后检验魔方是否还原回来。


5、 从原理上,我们首先得到各个操作码的逆操作码,即操作完 V 之后操作~V
能够回到原始状态。如下表所示:这些操作码三个一组,分管一个面的操作:


V
0
1
2
3
4
5
6
7
8
~V
2
1
0
5
4
3
8
7
6
V
9
A
B
C
D
E
F
G
H
~V
B
A
9
E
F
C
H
G
F


6、 得到解密还原的操作码序列如下:46F911C144FG147E234CFADC,另外我们知道如果连续的 2 个操作码是操作同一个面,那这 2 个操作码其实可以进行运算消除合并, 46F911C144FG147E234CFADC 中的 11 操作是第零个面连续转了 2 个 180°,可以消除舍去, 44 操作也是第一个面连续转了 2 个 180°,消除舍去, FG 操作是第五个面转了 180°后再转 270°,等价于转了 90°,化简为 H, 34 操作化简为 5 操作, DC 操作化简为 E 操作,化简合并之后得到最短的还原操作步骤如下:46F9C1H147E25CFAE,将这个值当成 18 进制(左低位右高位)转换成 62 进制(左低位右高位)得到口令:CcLaoE37J45Y 


7、 魔方还原的操作步法不唯一,本题通过后面的最后一步的校验保证其唯一性,解出此题的一个关键是发现化简环节。工作流程图如下所示:



反调试技巧


本题的反调试使用了一个小技巧, int 2d 指令触发一个异常信号,在调试和
跟踪环境下则不会触发该异常,会走到一个迭代 1000 次 base64 编码的编码过 程,然后将输入与字符串“ Vm0wd2QyUXlVWGw==”比较,这个是永远不会成立的,因为正确的编码结果是“ Vm0wd2QyUXlVWGw=”,对应的输入是
“ ImBeDebuged” ,而比较的字符串多了一个 ” =“号。 此处容易诱导解题者进
入解题误区。



破解过程


1、 定位到 0x406FC3 位置的校验函数;


2、 分析 0x40700B 位置调用魔方初始化函数和 0x407030 位置调用的魔方打
乱函数,该函数位于 0x4084A3 位置,根据操作步骤调用 0x4080DF 处的函
数,根据参数旋转指定的面和转动角度。

参数 KanXueCrackMe2017,打乱步骤 EDAHE450C741GH441E11BH84


3、 分析 0x40718B 位置调用的魔方还原函数,与打乱函数相同,参数是用户
的输入,对应还原步骤。按照打乱步骤的逆序和逆操作码,得到一个还原
序列46F911C144FG147E234CFADC,得到对应的输入ieunV2phk6yPywNtJ,测试得到如下结果:

给出了提示,不是失败,而是接近成功,说明思路是对的。
另外从下面的代码看出输入字符串长度为 0xC,即 12 个字符,小于上述
逆推出来的 17 个字符。



4、 最后一 个坑。


序列 46F911C144FG147E234CFADC 是可以化简的,
46F911C144FG147E234CFADC 中的 11 操作是第 0 面连续转了 2 个 180°,可以消除舍去, 44 操作也是第 1 面连续转了 2 个 180°,消除舍去, FG 操作是第 5 面转了 180°后再转 270°,等价于转了 90°,化简为 H, 34 操作化简为 5 操作, DC 操作化简为 E 操作,化简合并之后得到更短的还原操作步骤如下:46F9C1H147E25CFAE,将这个值当成 18 进制(左低位右高位)转换成 62 进制(左低位右高位)得到口令:CcLaoE37J45Y, 刚好 12个字符, 验证成功。








下面选取攻击者 jackandkx 的破解分析






相关工具:IDA、OD、python



一、按钮事件处理函数


由程序图标得知这是一个MFC程序。打开程序,随便输入sn,弹出失败对话框。


用OD打开CM,bp MessageBoxW,运行,输入sn,点击确定,触发MessageBoxW断点。栈回溯确定调用源0x407245,随即找到按钮处理函数0x4071fd。

主函数逻辑很简单,判断sub_406fc3的返回值。0弹出“失败”,1弹出“成功”,2弹出“你就差一点啦”



二、int 2d反调试


跟进0x406fc3函数,在正常流程中发现int 2d指令



int 2d反调试原理很简单,正常运行时int 2d触发异常,进入程序的异常处理函数。而当调试运行时,OD会处理该异常,将eip+1继续运行。

下图是CM设置的异常处理函数

patch掉int 2d,修改为jmp 0x40717d即可正常调试。



三、抽丝剥茧,理清程序脉络


异常处理函数中有3个关键判断


判断1:(失败返回0,成功则进入判断2)

判断2:(失败返回2,成功则进入判断3)

判断3:(失败返回2,成功则返回1,整个CM校验成功)

判断1是CM最重要的部分,下面我会详细分析判断1。


作者设置判断2是为了防止程序多解。事实上,如果在分析理清了作者的算法思路,那么逆推得出的sn会自然的pass掉判断2。

判断3的逻辑一目了然,eax指向sn字符串,判断条件:strlen(sn)=0xc。同判断2,这也是一个防止多解的判断。按作者思路逆推的sn也会pass掉判断3。


下面是判断 1 的详细分析:

判断 1 的成功条件:

为了便于描述,设var_d9f4开始,大小为0x30的字节流为BLOCK1。var_d934开始,大小为0x30的字节流为BLOCK2。

成功条件就是:BLOCK1和BLOCK2全等。



四、BLOCK1 和BLOCK2 的初始化


在0x40718b处下断,调试发现BLOCK1和BLOCK2都被初始化过。BLOCK1被初始化为0x00-0x2F依次递增排列,BLOCK2被初始化为0x00-0x2F的乱序排列。


往前翻代码,发现如下代码:

调试发现,sub_4084A3就是初始化BLOCK1和BLOCK2的函数。初始化时,sub_4084A3被调用(传入了字符串参数”KanXueCrackMe2017“,传入了BLOCK1的地址)(事实上,BLOCK1和BLOCK2在内存中是紧挨着的,实际上做变换的是BLOCK2),判断1前,sub_4084A3再次被调用(传入了我们的sn字符串,传入了BLOCK1的地址)。


为了使判断1成功,要让BLOCK2和BLOCK1全等。调试发现,sub_4084A3并不会打乱BLOCK1,只会打乱BLOCK2。(BLOCK1一直为0x00-0x2F的递增排列)


所以我们要找的sn可以说是字符串”KanXueCrackMe2017“在函数sub_4084A3作用下的”逆“。 ”KanXueCrackMe2017“ 负责打乱递增排列的BLOCK2,而我们的SN则负责还原BLOCK2。



五、SN变换


在打乱BLOCK之前,SN会经历4步变换。


SN的第一次变换:


进入sub_4084A3

进入sub_40829c

对sn中的每一个char做判断:

  • 在'0'~'9' 之间则减去'0'。结果范围[0,9]

  • 在'A'~'Z'之间则减去'7'。结果范围[10,35]

  • 在'a'~'z'之间则减去'='。结果范围[36,61]


变换1:由字符向[0,61]区间做1对1映射。


SN的第二次变换:


同样是在sub_40829c中

第一个call sub_403641作用是初始化变量。

第二个call sub_4038E1读取向[0,61]区间映射过的sn,按位权重乘以相应个数的62。

最后两个call将这些按62位权重的数求和。

变换2:转换为62进制数字


SN的第三次变换:

变换3:62进制转换为18进制


SN的第四次变换:

变换4:[0,17]向[0-9,'A'-'H']做1对1映射


验证代码:

为了确认这4次SN的变换,通过调试,得到输入字符串” ”KanXueCrackMe2017 “,得到输出字符串"EDAHE450C741GH441E11BH84"


验证代码如下(python实现):

输出如下:


验证通过



六、BLOCK 变换


在之前的代码中,我们的SN被变换为SN1。下面我们来看SN1是如何引导BLOCK的变换的。


SN1变换后作为sub_4080DF的参数:

SN1又被转换为了[0,17]的数字序列,每个数字除以3的商和余数作为参数传递给sub_4080DF


进入sub_4080DF(函数较长,仅截取一部分):


这种函数中就调用了一个函数sub_40727D,余数决定了调用的次数,商决定了传给该函数的01块的地址。


余数的范围[0,2],调用次数为余数+1,即[1,3]。[0,17]除以3的范围是[0,5],相对应,也有6个不同的01块。


进入sub_4072:


调试发现sub_40727d就是BLOCK变换的执行者。下文简称基函数。上图基函数有两个变量,传递进来的都是BLOCK2的地址。


但事实上,最关键的一个参数IDA并没有识别出来,就是图中的v2,通过ecx传递进来的。这个v2是一个大小为0x2400的由0和1的DWORD值组成的块。


观察上图代码,基函数通过局部变量v10保存数据,退出时,用v10覆盖BLOCK2。v10中的每个值都是由01块v2和原BLOCK2对应求积再求和而来,这0x30个积中,01块有且仅有一个为1。每次算出一个值之后,会对01块进行的错位。通过这种方式来保证每个BLOCK2中的值都能通过01块映射到v10中。就这样,基变换完成了对BLOCK2的一次置换。


01块的初始化:

01块的初始化在sub_407307中:

上图只是一个01块的初始化(一共有6个01块)

6个01块,对应着6种基函数。把置换表提取出来:


七、拨云见日,算法模型浮出水面


提取出置换表之后,观察置换表特点

1、有一行置换后不变

2、有一行发生了偏移为2的移位。

3,、其余4行都只有3个位置产生了置换,剩余5个位置不变。

然后就。。。。

3X3魔方6个面对应6个置换表。旋转一个面时,对立面不变,旋转面偏移2移位,其余4面变换3位。


去除中心节点,魔方共有6X(9-1)=48=0x30个小方块。完美契合CM中的置换函数。



八、建立模型,还原魔方求SN

还是用python:

结果:



SN:CcLaoE37J45Y


— END —


温馨提示

每道题结束过后都会看到很多盆友的精彩解题分析过程,因为公众号内容的限制,每次题目过后我们将选出一篇与大家分享。解题方式多种多样,各位参赛选手的脑洞也种类繁多,想要看到更多解题分析的小伙伴们可以前往看雪论坛【CrackMe】版块查看哦!



热门推荐| 看雪CTF





您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存